package com.ting.test.algorithms.排序算法;

/**
 * 将数组按照从小到大的方法排列
 * 插入排序：
 * 核心思想
 * 从0~n-1中选择出最小的放到0位置
 * 从1~n-1中选择出最小的放到1位置
 * 从2~n-1中选择出最小的放到2位置
 * 以此类推
 * 具体步骤
 * 1.从左到右，将i+1~n-1位置的元素依次和i进行比较，如果小则替换，=
 * 每遍历1次，则i位置的元素会被确定
 * 时间复杂度为O(n^2)  等差数列 a*n^2 +b*n +c
 * 空间复杂度O(1)
 */
public class 冒泡排序 {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 14, 21, 13, 567, 88, 54, 34, 2, 3};
        int[] result = selectSort(arr);
        System.out.print("arr=[");
        for (int res : arr) {
            System.out.print(res + ",");
        }
        System.out.println("]");

        System.out.print("result=[");
        for (int res : result) {
            System.out.print(res + ",");
        }
        System.out.println("]");
    }

    private static int[] selectSort(int[] arr) {
        if (arr == null || arr.length == 1) {
            return arr;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[i]) {
                    swap(arr, i, j);
                }
            }
        }

        return arr;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

    }
}
